Differentially Private Analysis of Outliers

摘要

This paper investigates differentially private analysis of distance-basedoutliers. The problem of outlier detection is to find a small number ofinstances that are apparently distant from the remaining instances. On theother hand, the objective of differential privacy is to conceal presence (orabsence) of any particular instance. Outlier detection and privacy protectionare thus intrinsically conflicting tasks. In this paper, instead of reportingoutliers detected, we present two types of differentially private queries thathelp to understand behavior of outliers. One is the query to count outliers,which reports the number of outliers that appear in a given subspace. Ourformal analysis on the exact global sensitivity of outlier counts reveals thatregular global sensitivity based method can make the outputs too noisy,particularly when the dimensionality of the given subspace is high. Noting thatthe counts of outliers are typically expected to be relatively small comparedto the number of data, we introduce a mechanism based on the smooth upper boundof the local sensitivity. The other is the query to discovery top-$h$ subspacescontaining a large number of outliers. This task can be naively achieved byissuing count queries to each subspace in turn. However, the variation ofsubspaces can grow exponentially in the data dimensionality. This can causeserious consumption of the privacy budget. For this task, we propose anexponential mechanism with a customized score function for subspace discovery.To the best of our knowledge, this study is the first trial to ensuredifferential privacy for distance-based outlier analysis. We demonstrated ourmethods with synthesized datasets and real datasets. The experimental resultsshow that out method achieve better utility compared to the global sensitivitybased methods.